package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
        int[] nums1 = {1, 2, 3, 2, 1};
        int[] nums2 = {3, 2, 1, 4, 7};

        Solution s1 = new Solution();
        System.out.println(s1.findLength(nums1, nums2)); // 3

        Solution2 s2 = new Solution2();
        System.out.println(s2.findLength(nums1, nums2)); // 3
    }

    // 最长重复子数组 - 动态规划 O(m * n)
    static class Solution {
        public int findLength(int[] nums1, int[] nums2) {
            // 1) 边界处理
            if (nums1 == null || nums2 == null) return 0;
            int m = nums1.length, n = nums2.length;
            if (m == 0 || n == 0) return 0;

            // 2) dp[i][j] 表示 nums1 从 i 开始、nums2 从 j 开始的最长公共前缀长度
            int[][] dp = new int[m + 1][n + 1];
            int ans = 0;

            // 从后往前枚举，保证可以用到 dp[i + 1][j + 1]
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    if (nums1[i] == nums2[j]) {
                        dp[i][j] = dp[i + 1][j + 1] + 1;
                        if (dp[i][j] > ans) ans = dp[i][j];
                    }
                }
            }
            return ans;
        }
    }

}